package com.year_23.april;

import java.util.HashMap;

/**
 *
 * 70 爬楼梯的方法
 *
 *      https://leetcode.cn/problems/climbing-stairs/
 * @Author jsh
 * @Date 2023/4/19 22:41
 * @Version 1.0
 */
public class Day19_3 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(climbStairs(6));


        for (int i = 1; i < 50; i++) {
            if (sumWay(i) == climbStairs(i))
                System.out.println(i);
        }

        System.out.println(start - System.currentTimeMillis());
    }

    public static int sumWay(int n){
        if (n == 1 || n == 2)return n;
        int sum = 0;
        int one = 1;
        int two = 2;
        for (int i = 3; i <= n; i++) {
            sum = one + two;
            one = two;
            two = sum;
        }
        return sum;
    }

    static HashMap<Integer, Integer> map = new HashMap<>();
    public static int climbStairs(int n) {
        if (n == 1 || n ==2)return n;
        if (map.containsKey(n))
            return map.get(n);
        int res = climbStairs(n-1) + climbStairs(n-2);
        map.put(n,res);
        return res;
    }
}
